Field of the Invention
This invention relates to apparatus and methods for storing and organizing data in a computer system.
Background of the Invention
Applications often need to be able to work with variable-sized collections of data. Such collections of data could have zero, one, or potentially millions of data entries. Well-written applications typically provide collections that can grow as the needs of the application change. For applications that are multi-threaded, there are additional complexities to efficiently manage collections because data entries may be added or updated in such collections by different threads simultaneously. As a result, in multi-threaded applications, the underlying collections typically require synchronization (e.g., locks, etc.) of some form to ensure that data integrity is maintained.
These issues are addressed today with a variety of collections that have different performance characteristics. One of the most convenient and oft-used collections is the simple one-dimensional array. The downside of such an array is that, when the array is full, a new array must be allocated, and the data in the old array must be copied to the new array. In a multi-threaded environment, all threads that need to add data to the collection will need to wait for the copy to complete, or alternately, write to a secondary array in the meantime. This can substantially hinder performance in the multi-threaded environment. A two-dimensional (or higher) form of array may also be used. However, such arrays are simply mapped to one-dimensional arrays by compilers. Thus, such arrays have many if not all of the shortcomings discussed above with respect to one-dimensional arrays.
In view of the foregoing, what is needed is an array data structure that overcomes the shortcomings of conventional arrays, such as single or multi-dimensional arrays. Ideally, such an array data structure could grow over time while avoiding or minimizing the use locks or other synchronization mechanisms to access data therein.